The present invention generally relates to the field of electronic communications. More specifically, the present invention relates to communication protocol systems and methods used in such electronic communications.
The Internet protocol (IP) is the standard protocol for carrying out data transmission over the Internet. Prior art FIG. 1 shows an open system interconnect (OSI) model 100 that depicts the different layers of processing involved in IP data communication within a gateway or host computer. The model 100 includes application 102, presentation 104, session 106, transport 108, network 110, data link 112, and physical 114 layers. Each layer understands a certain communication protocol, which among other things contains a specific packet format. Each layer also employs a standard method of encapsulating and de-encapsulating packets received from upper and lower layers. When a layer receives a packet of data from an upper layer, that layer encapsulates the packet into a new packet conforming to the packet format the layer understands. The layer then passes the new packet to the next lower layer. When a layer receives a packet of data from a lower layer, the receiving layer retrieves (i.e., deencapsulates) the encapsulated inner packet and passes it to the next upper layer.
Prior art FIG. 2 shows a group of diagrams 200 that illustrate encapsulation at various layers of model 100 as an example of UDP/IP over Ethernet, i.e., from the transport layer 108 to the network layer 110 and then to the data link layer 112. At the transport layer 108, a UDP packet 220 includes a UDP header 202 and data 210. At the network layer 110, the IP packet 230 includes the UDP packet 220 and an IP header 204. And, at the data link layer 112, the IP packet 230 is encapsulated in an Ethernet header 206 and trailer 208, as an Ethernet frame 240. The Ethernet frame 240 is transmitted to a physical network connection. It can be seen from FIG. 1 and FIG. 2, for each layer of encapsulation the packet size is increased, which means more bandwidth is consumed. For example, the Ethernet header 206 and trailer 208 together add 26 bytes. That is, for each IP packet transmitted, there will be 26 bytes of overhead in Ethernet framing.
FIG. 3 illustrates an example of prior art data communication between nodes, e.g., gateway/host A 310 and gateway/host D 340, which includes transit through gateway B 320 and gateway C 330. The data-link layer technologies employed by each connection may be different. For illustrative purposes, assume the direction of data communication is from gateway/host A 310 to gateway/host D 340. For each frame of data received in a gateway (e.g., gateway 320 or 330), the gateway needs to determine (referred to as routing) which gateway in the next hop to send the data, and may need to retrieve the IP packet from the frame and encapsulate the IP packet in a different data-link framing technology before relaying it to the next hop gateway. Such processing consumes computing power and memory and causes transmission delay. If data traffic is heavy in a gateway, the gateway may not be able to transmit the data as fast as it is received and network congestion and delays result due to excess contention for limited gateway resource and bandwidth.
IP header compression is a prior art technique that can reduce a packet""s size and result in more efficient packet transportation. There are some Internet standard methods for IP header compression, such as IP/TCP header compression (RFC 1144) and IP/UDP/RTP header compression (RFC 2508). Header compression relies on many fields in the header being constant or changing seldomly in consecutive packets belonging to the same packet stream. Fields that do not change between packets need not be transmitted at all. To initiate compression of the headers of a packet stream, a full header carrying a context identifier (CID), is transmitted over the link. The compressor and decompressor store most fields of this full header in a context structure and the CID to be associated with the context structure. The context structure comprises the fields of the header whose values are constant and thus need not be sent over the link at all, or change little between consecutive headers so that it uses fewer bits to send the difference from the previous value compared to sending the absolute value. After context structure and its CID has been synchronized between the compressor and the decompressor, the compressor can then compress packet headers by computing the difference between the headers and the initial values stored in the context structure and encoding only the non-zero values of the difference. After receiving the compressed header together with the CID, the decompressor retrieves the context structure using the CID and decompresses the compressed header. Header compression is most effective for small packets where the overhead header is significant. The problem with IP header compression is that, the compressed packet is no longer a standard IP packet and it depends on the data-link layer to carry the compression information such that the receiving node can decompress the header and recover the original packet. This requires that the receiving node.must have a data-link layer direct connection with the sending node. Therefore, IP header compression has been applied only on a link-by-link basis. In today""s public Internet, packet may traverse over many intermediate routers before reaching the receiving node. As shown in FIG. 3, packets originated from Node A 310 traverse over Node B 320 and Node C 330 before reaching Node D 340. Therefore, IP header compression cannot be applied just between Node A 310 and Node D 340.
IP payload compression (IPComp) is another prior art technique for improving packet transportation efficiency. IPComp is an Internet standard method (RFC-2393). IPComp reduces the size of IP payload before passing the IP packet to the data-link layer, and therefore increases the overall communication performance between a pair of communicating hosts/gateways (xe2x80x9cnodesxe2x80x9d). The IPComp protocol operates at the network layer 110 in the OSI model 100, illustrated in FIG. 1.
The compression processing of IP packets has two phases: compressing of outbound IP packets (xe2x80x9ccompressionxe2x80x9d) and decompressing of inbound IP packets (xe2x80x9cdecompressionxe2x80x9d). The compression processing must be loss-less, ensuring that the IP packet, after being compressed and decompressed, is identical to the original IP packet. Additionally, the compression processing must enforce a non-expansion policy, that is, if the compressed packet is larger than the original packet, the original packet will be transmitted.
The data link layer typically imposes a maximum transmission unit (MTU). For example, the Ethernet has a MTU of 1500 bytes. The non-expansion policy ensures the packet would not exceed the MTU, which would cause packet fragmentation and result in increased overhead. Each IP packet is compressed and decompressed by itself without any relation to s other packets (xe2x80x9cstateless compressionxe2x80x9d), as IP packets may arrive out of order or not arrive at all. Each compressed IP packet encapsulates a single IP payload.
An original IP packet 400 is shown in prior art FIG. 4A. IP packet 400 is shown in a compressed form 420 in FIG. 4B, in accordance with the prior art protocol IPComp. The compressed IP packet 420 contains a modified IP header 422, an IPComp header 424, and compressed.payload data 426. The payload data 426 may be compressed using any known loss-less compression algorithm. The modified (indicated by the asterisk) IP header 422 shown in FIG. 4B contains a new protocol identification, which is used by the remote node to identify the packet as an IPComp compressed packet. The modified IP header 422 also contains new value of total length and header checksum for the compressed IP packet 420.
As shown in prior art FIG. 4C, an IPComp header 450 consists of four-octets, 0 through 3 (i.e., 4 bytes), where the field 452 stores an IP (v.4) protocol field or an IP (v.6) Next Header field of the original IP header; the xe2x80x9cFlagsxe2x80x9d fields 454 is typically reserved and set to zero; the xe2x80x9cCompression Parameter Indexxe2x80x9d (CPI) field 456 identifies the compression algorithm used. The remote node receiving the compressed IP packet will choose the correct decompression algorithm according to CPI 456.
To utilize the IPComp protocol, two nodes must first establish a compression association (CA) between them. The CA includes all required information for the operation of IPComp, including the CPI, the mode of operation, the compression algorithms to be used, and any required parameter for the selected compression algorithm. Generally, IPComp operation is known in the art, so not discussed in detail herein.
One problem with IPComp is that it requires each IP packet to be compressed individually without any relation to other packets. This requirement limits the ability to compress IP data, so a certain amount of inefficiency generally has been tolerated, as being unavoidable.
The invention is a system and method for group packet encapsulation and (optionally) compression. The system and method increase packet transmission performance between two gateways or host computers by reducing data-link layer framing overhead, reducing packet routing overhead in gateways, reducing packet header overhead, and increasing loss-less data compression ratio beyond that otherwise achievable with standard protocols, such as IPComp. To accomplish this, the system and method implement an encapsulation protocol of the present invention, which, as an-example, can be used with IP packets, as a group IP packet encapsulation and (optionally) compression (GIEC) system and method.
In many situations, a communication device (e.g., node) may accumulate multiple packets in its internal queue before passing them to the data link layer. The packet accumulation could be the result of, as examples, a TCP/UDP protocol sending multiple packets at the same time, network congestion blocking packets in queue, multiple TCP/UDP flows transmitting simultaneously between two nodes (e.g., gateways/hosts) or some combination thereof.
In accordance with the encapsulation protocol, two communication nodes (e.g., a Node-X and a Node-Y) establish one or more protocol xe2x80x9cassociationsxe2x80x9d. A node could be a gateway, host computer or some other known communication device. In this example, Node-X and Node-Y may be configured with modules that implement the system, method, and protocol of the present invention. Node-X establishes a protocol association for-Node-Y. Among other things, a protocol association for Node-X includes an address map. The address map comprises a list of addresses of nodes for which packets transmitted from Node-X can pass through to get to Node-Y. An address for a node could be an address for an end system or a subnet address representing a sub-network, as examples. Similarly, Node-Y can establish a protocol association for Node-X. For packets being transmitted from Node-X to Node-Y, only one protocol association is required.
In accordance with the present invention, when Node-X is preparing to transmit packets, Node-X determines which of those packets has a destination address that matches an address in the address map. The packets are grouped according to having a common destination or intermediate node in their path. For a given node address (e.g., Node-Y) in the address map, Node-X dynamically combines the group of packets into one encapsulation packet with one encapsulation packet header and one encapsulation payload. The encapsulation payload contains the original packet headers and payloads. Node-X may optionally compress at least a portion of the original packet headers and/or payloads in the encapsulation payload, according to known compression techniques. The encapsulation packet header contains a special protocol identifier referred to as an encapsulation packet protocol ID. Node-X transmits the encapsulation packet to, in this example, Node-Y. When Node-Y receives the encapsulation packet, the encapsulation packet protocol ID (or other information encoded in the encapsulation packet) is used by Node-Y to identify the received packet as an encapsulation packet in accordance with the present invention. Node-Y retrieves the encapsulation payload, decompresses the payload, if it has been compressed, and then de-encapsulates the encapsulation payload. After de-encapsulating, Node-Y recovers the original group of packets and forwards them to the appropriate gateways or end systems. That is, for those packets for which Node-Y is not the ultimate destination, the packets are sent on to their destinations from Node-Y.
The system and method of the present invention, implementing the encapsulation protocol, improves transmission performance in a variety of manners. For example, data link framing overhead is reduced, which results in reduced bandwidth consumption. That is, instead of incurring n framing overheads for n packets, by encapsulating these n packets into one packet, there will be only one framing overhead. Additionally, packet routing overhead in gateways is reduced. Instead of incurring n overheads in routing n packets, by encapsulating these n packets into one encapsulation packet, there is one overhead, as if routing only one packet. And, because the encapsulation IP packet is a regular IP packet that can traverse any intermediate routers in an IP network, IP header compression can be applied on IP packets contained in the encapsulation payload without requiring Node-X and Node-Y to have a direct data-link connection. Also, if compression is applied in IP payloads-contained in the encapsulation payload, the set of data that comprise these payloads can be compressed together, rather than compressing each IP packet payload individually, as is done in the prior art systems. As a result, the compression ratio may be increased, because more data are compressed together within a single packet, resulting in reduced bandwidth consumption.
The encapsulation protocol may further employ an intelligent adaptive algorithm (IAA) to prevent the encapsulated and (optionally) compressed packet from-exceeding the MTU. Exceeding the MTU causes packet fragmentation and re-assembly, which inevitably introduces overhead in processing and bandwidth. The IAA, at a macro level, includes at least two steps. First, the compression ratio for packet header compression and payload compression for packets destined for the same remote node is estimated dynamically. The compression ratio is defined as the size of buffer before compression divided by the size of buffer after compression. The compression ratio can be estimated from compression ratios obtained from the previous packets. The compression ratio can also be continuously updated as an average, over a chosen window of time. If no compression is applied, the compression ratio can be set to 1, referred to as xe2x80x9cnullxe2x80x9d compression. Second, a determination is made of the maximum length of the encapsulation packet before compression is applied. The maximum length determines how many packets can be encapsulated together without exceeding the MTU. The maximum length is determined based on the known MTU for the corresponding link and the estimated compression ratio.
Preferably, the encapsulation protocol is backward compatible with known protocols, such as IPComp. That is, the system and method of the present invention may employ a protocol ID that is adapted from a protocol ID otherwise assigned to a known protocol (e.g., IPComp). In such a case, the encapsulation protocol employs special values in the CPI for identifying, as an encapsulation protocol, a known protocol. As an example, a standard IPComp header contains a 16-bit CPI that identifies a compression algorithm. The known IPComp standard, defined in RFC-2393, allocates CPI values 0-63 for well-known compression algorithms and allocates values 61440-65535 for private use among cooperating parties. As an example, the encapsulation protocol may designate a value range, in the unassigned value range of 61440-65535, to identify the encapsulation protocol. CPI values in this range may be referred to as encapsulation CPI values. Multiple sets of value ranges can be assigned, for example, (61440+D*100)-(61540+D*100xe2x88x921), where D=0,1,2. . . is the ID of the range, and each range has 100 values, for example. Different D values may designate different encapsulation schemes, while the values in the range may designate different payload compression algorithms. An encapsulation scheme specifies the format with which multiple IP packets are encapsulated into one IP packet. For example, D=0 may represent a specific encapsulation scheme, and values 61440-61503 may correspond to the same well-known payload compression algorithms reserved in CPI values 0-63, and values 61504-61539 may designate other compression algorithms. Therefore, if a CPI value is 61440, it can be known that group packet encapsulation in accordance with the present invention and a known encapsulation scheme (D=0) has been applied, and the payload compression algorithm is the well-known algorithm identifier 0.
When header compression is applied, the encapsulation scheme may insert a header compression (HC) header before each packet header contained in the encapsulation packet. The HC header may contain one or more bytes that comprise information of header compression scheme ID, encoding scheme ID, size of the following header, and context identifier (CID). Header compression schemes specify types of header compression such as Null-header-compression, IP-TCP header compression, IP-UDP header compression, and IP-UDP-RTP compression, etc. Null-header-compression indicates that the following header is not compressed, which allows selective header compression in one encapsulation packet. Encoding schemes specify encoding algorithms used for encoding compressed headers. If an implementation will support only one encoding scheme for each header compression scheme, it is not necessary for the HC header to include an encoding scheme ID. A specific encapsulation scheme may also indicate whether any header compression has been applied or not, and therefore whether a HC header has been inserted before each packet header or not in the encapsulation packet.
With the encapsulation protocol of the present invention, header and/or payload compression can be optional. Group packet encapsulation, even without compression, significantly increases communication performance in most cases, especially when each encapsulated packet is short. Group packet encapsulation reduces the overheads associated with data link layer framing and with packet routing. Therefore, unlike the IPComp protocol, as an example, the encapsulation protocol of the present invention can be applied to payload data that is not compressible, such as speech and video data in voice and video over IP communications. Group packet encapsulation combining with header and/or payload compression can further reduce the encapsulation packet size and therefore achieve higher performance.
To allow the same encapsulation protocol to support optional payload compression, the encapsulation protocol can further designate a special encapsulation CPI value to denote group packet encapsulation with null payload compression. For example, the value 99 in each range (61540+D*100xe2x88x921), where D=0,1,2. . . can be used for the null payload compression encapsulation CPI. xe2x80x9cNull payload compressionxe2x80x9d means that packet payloads contained in the encapsulation packet are not compressed. The same encapsulation protocol can also support optional packet header compression by using special encapsulation scheme IDs (i.e., D values) to designate null header compression. xe2x80x9cNull header compressionxe2x80x9d means that packet headers contained in the encapsulation packet are not compressed.
As previously noted, the system and method of the present invention need not use or be backward compatible with the IPComp protocol. Depending on the application of the system, compatibility with other protocols may be favored and implemented in addition to or instead of IPComp, as will be appreciated by those skilled in the art.